Digital image processing involves the conversion of a continuous analog image field or other multi-dimensional data into an equivalent digital form. The physical image is spatially sampled to produce an array of numbers which can be processed into the reconstruction of a continuous image for viewing. An image can encompass both pictorial data and analytical data from, for example, physical, medical or seismic processes. For images in motion, digital samples can also be time varying. The rate of sampling is typically equal to or greater than twice the highest frequency component in the moving image, i.e., at the Nyquist rate. Over-sampling (i.e., sampling at higher than the Nyquist rate) is often the rule.
Two-dimensional (2-D) images are commonly encoded raster fashion by scanning row-by-row (horizontally) across columns (vertically) of image spots. Scanned points called pixels are positionally defined by discrete horizontal and vertical pairs of coordinate numbers. Each pixel is sampled to produce a digital number quantized to its intensity or density. An array of such numbers encodes the finite field of the overall 2-D image. Due to various distortions, such as quantization errors, non-uniform illumination of the image, thermal noise and impulse noise, the stored encoded image is less than perfect.
In order to reproduce the scanned image in a manner that is acceptable to an observer or to analytical systems, the stored numerical data often must be processed digitally. Such processing is called convolution and the apparatus for implementing convolution is called a convolver.
Two-dimensional (2-D) convolution is widely employed in image processing for noise filtering, feature enhancement, and image restoration. As a first step in convolution of encoded data, including raster-encoded data, adjacent pixels on a succession of scanned rows or horizontal lines are ordered into kernels of pixels in an m x n array, where m may be set equal to n in order to square the kernel. As scanning proceeds the kernels slide along the image first horizontally and then vertically. Each kernel can be masked by a predetermined matrix of coefficients to replace the kernel at a central location, for example, with a single composite value that tends to smooth the image and substantially eliminate single-pixel noise, which might otherwise show up in the reproduced image as undesired blips of non-correlated noise (e.g., white or "snow"). In this manner each pixel is compared with its surrounding neighbors and appropriately adjusted.
Processing each kernel in real time requires a number of multiplications equal to the number of pixels in a kernel and an accumulation of the resulting products. In performing a multiplication, the number of bits in a product is double the number of bits in the coefficient. The accumulated products can later be truncated or rounded to the number of bits in the original sample, as necessary.
In a known direct embodiment, a 2-D convolver operates on a serial stream of sampled data from a raster scanned image fed into sequential delay lines of horizontal-line length. An m x n or (m-1) x n array of pixel-wide delay elements receives, respectively, an undelayed data stream representing the leading m pixels of a current horizontal line, a data stream delayed by one horizontal-line length representing m adjacent pixels of an immediately prior horizontal line, a data stream delayed by two horizontal-line lengths representing m further adjacent pixels of the second prior horizontal line, and so forth up to n-1 horizontal-line delays. Each sample at the output of a pixel delay element is multiplied by a coefficient to form a product value. The product values of each kernel are summed in a plurality of adders to form the composite scaled output.
This prior art direct embodiment has the disadvantage that the adders in the same horizontal rows and vertical columns are serially connected. Each adder has an inherent constant delay d and the adder delays are cumulative. The result for a squared kernel of order N is a delay of 2(N-1) times the unit delay d. This 2(N-1)d delay magnitude is significant and limits the operating speed of the convolver. In large order convolvers, such a delay can become unmanageable.
It is desirable to have a hybrid convolver structure which avoids the foregoing cumulative delays and thereby improves image processing efficiency.